﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Demo.Framework.Problems.Percolation
{
    class Grid
    {
        private int _count;
        private int _n;
        private int[] _array;
        private int[] _size;
        private int[] _state;

        private int _virtualTop;
        private int _virtualBottom;

        public Grid(int N)
        {
            _n = N;
            _count = (int)Math.Pow(N,2);
            _array = new int[_count + 2];
            _size = new int[_count + 2];
            _state = new int[_count + 2];

            for (int i = 0; i < _count; i++)
            {
                _array[i] = i;
            }

            _virtualTop = _count;
            _virtualBottom = _count + 1;

            Initialize();
        }

        private void Initialize()
        {
            _state[_virtualBottom] = 1;
            _state[_virtualTop] = 1;

            _array[_virtualBottom] = _virtualBottom;
            _array[_virtualTop] = _virtualTop;

            for (int i = 0; i < _n; i++)
            {
                Union(i,_virtualTop);
            }

            for (int i = _count-1; i >= _count - _n; i--)
            {
                Union(i,_virtualBottom);
            }
        }

        private int Root(int i)
        {
            while (i != _array[i])
            {
                //_array[i] = _array[_array[i]];
                i = _array[i];
            }

            return i;
        }

        /// <summary>
        /// Union - Path compression with weighted quick union
        /// </summary>
        /// <param name="p"></param>
        /// <param name="q"></param>
        /// <returns></returns>
        private bool Union(int p, int q)
        {
            try
            {
                int root_p = Root(p);
                int root_q = Root(q);

                if (_size[p] <= _size[q])
                {
                    _array[p] = root_q;
                    _size[q] += 1;
                }
                else
                {
                    _array[q] = root_p;
                    _size[p] += 1;
                }

                return true;
            }
            catch (Exception)
            {                
                return false;
            }
        }

        private bool IsConnected(int p, int q)
        {
            return Root(p) == Root(q);
        }

        private int GetLeft(int i)
        {
            if (i % _n == 0)
            {
                return -1;
            }            

            return i - 1;
        }

        private int GetRight(int i)
        {
            if ((i+1) % _n == 0)
            {
                return -1;
            }

            return i - 1;
        }

        private int GetUp(int i)
        {
            if (i - _n < 0)
            {
                return -1;
            }
            else
            {
                return (i - _n);
            }
        }

        private int GetDown(int i)
        {
            if (i + _n > _count)
            {
                return -1;
            }
            else
            {
                return (i + _n);
            }
        }

        /// <summary>
        /// Opens a Node
        /// If the N^2 elements are thought to be in N X N matrix        /// 
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        public bool Open(int p)
        {
            if (_state[p] == 1)
            {
                return false;
            }
            else
            {
                Console.WriteLine("Opening Node : {0}", p);
                _state[p] = 1;
                // check if there are other open nodes in the viscinity
                // up, down, left, right
                int up = GetUp(p);
                int down = GetDown(p);
                int left = GetLeft(p);
                int right = GetRight(p);

                if (up != -1)
                {
                    if (_state[up] == 1 )
                    {
                        Console.WriteLine("Connecting Up : {0} , {1}", p, up);
                        Union(up, p);
                    }
                }

                if (down != -1)
                {
                    if (_state[down] == 1)
                    {
                        Console.WriteLine("Connecting Down : {0} , {1}", p, down);
                        Union(down, p);
                    }
                }

                if (left != -1)
                {
                    if (_state[left] == 1)
                    {
                        Console.WriteLine("Connecting Left : {0} , {1}", p, left);
                        Union(left, p);
                    }
                }

                if (right != -1)
                {
                    if (_state[right] == 1)
                    {
                        Console.WriteLine("Connecting Right : {0} , {1}", p, right);
                        Union(right, p);
                    }
                }

                return true;
            }
        }

        public bool IsPercolating()
        {
            return IsConnected(_virtualTop, _virtualBottom);
        }
    }
}
